//package com.xyhuo.leetcode.december;
//
//import java.util.*;
//
///**
// * 格雷编码
// * https://leetcode.cn/problems/gray-code/
// *
// * @time 2023/12/29
// */
//public class GrayCode {
//
//    public static void main(String[] args) {
//        GrayCode gc = new GrayCode();
//        gc.grayCode(5);
//    }
//
//
//    private boolean find = false;
//
//    private List<Integer> ans = new ArrayList<>();
//
//    public List<Integer> grayCode(int n) {
//        int[] already = new int[(int) Math.pow(2, n)];
//        Deque<Integer> deque = new ArrayDeque<>(already.length);
//        generateGrayCode(deque, already);
//        return ans;
//    }
//
//    Map<String, Boolean> rem = new HashMap<>();
//
//
//    private void generateGrayCode(Deque<Integer> deque, int[] already) {
//        if (find) {
//            return;
//        }
//        int zeroCount = 0;
//        for (int i = 0; i < already.length; i++) {
//            if (already[i] == 0) {
//                zeroCount++;
//                if (deque.isEmpty()) {
//                    already[i] = 1;
//                    deque.addLast(i);
//                    generateGrayCode(deque, already);
//                    deque.removeLast();
//                    already[i] = 0;
//                } else {
//                    int lastVal = deque.getLast();
//                    if (onlyOneDif(lastVal, i)) {
//                        already[i] = 1;
//                        deque.addLast(i);
//                        generateGrayCode(deque, already);
//                        deque.removeLast();
//                        already[i] = 0;
//                    }
//                }
//            }
//        }
//        if (zeroCount == 0) {
//            if (onlyOneDif(deque.getLast(), deque.getFirst())) {
//                find = true;
////                ans.addAll(list);
//
//            }
//        }
//    }
//
//    private boolean onlyOneDif(int m, int n) {
//        String key = m < n ? m + "_" + n : n + "_" + m;
//        if (rem.containsKey(key)) {
//            return rem.get(key);
//        }
//
//        int diffCount = 0;
//        while (m > 0 || n > 0) {
//            if ((m % 2 == 0 && n % 2 == 1) || (m % 2 == 1 && n % 2 == 0)) {
//                if (diffCount > 0) {
//                    rem.put(key, false);
//                    return false;
//                }
//                diffCount++;
//            }
//            m = m >> 1;
//            n = n >> 1;
//        }
//        rem.put(key, true);
//        return true;
//    }
//}
